슬라이딩 윈도우를 이용한 최댓값 찾기(sliding window maximum, Deque Range Maximum Trick)
1. 문제 배열 A에서 길이가 K인 모든 연속하는 부분배열내에서 최댓값을 찾는 문제 [1,2,3,1,4,5]이고 K = 3인 경우를 생각해보자. [1,2,3]에서 최댓값은 3 [2,3,1]에서 최댓값은 3 [3,1,4]에서 최댓값은 4 [1,4,5]에서 최댓값은 5 배열의 크기가 작으면 매우 쉬운 문제지만, 배열의 크기가 크면 상당히 어려운 문제다. 투포인터로 구간의 시작과 끝을 잡고 첫 구간에서는 어떻게 O(K)로 최댓값을 찾아 놓은 다음.. 다음 구간으로 이동할텐데, 시작과 끝의 위치를 아니까, 시작 쪽의 원소를 버릴거고 끝의 원소를 추가할거고... 그런다고 하더라도 최댓값이 뭔지를 어떻게 알지? 운 좋게 시작과 끝에 최댓값이 있다고 하더라도... 구간 중간에 최댓값이 있는거라면 어쨌든 매 구간마다 ..
